//https://leetcode.cn/problems/guess-number-higher-or-lower-ii/submissions/582557447/
class Solution {
private:
    static const int MAX_SIZE = 200 + 5;
    int memo[MAX_SIZE][MAX_SIZE];
public:
    int getMoneyAmount(int n) {
        return dfs(1, n);
    }

    int dfs(int start, int end) {
        if (start >= end) {
            return 0;
        }

        if (memo[start][end] != 0) {
            return memo[start][end];
        }

        int ans = 0x3fffffff;
        for (int k = start; k <= end; k++) {
            ans = min(ans, max(dfs(start, k - 1), dfs(k + 1, end)) + k);
        }

        return memo[start][end] = ans;
    }
};
